package me.sealer.algorithm.utils.tree;

import me.sealer.algorithm.tree.BinaryTree;

import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * @author sealer
 */
public class BinaryTreeUtil {

    /**
     * 向二叉树中插入子节点,二叉树的根节点都比右节点小， 构建一棵二叉排序树 默认升序
     * 此为递归实现， 思考：如果不使用递归， 如何实现？
     *
     * @param root 树根节点
     * @param data 待插入节点
     */
    public static <T extends Comparable> void insert(BinaryTree<T> root, T data) {
        // 如果待插入节点大于当前节点， 则将该节点插入当前节点的右子树。
        if (data.compareTo(root.getData()) > 0) {
            BinaryTree<T> rightChild = root.getRightChild();
            if (rightChild == null) {
                root.setRightChild(new BinaryTree(data));
            } else {
                insert(rightChild, data);
            }
        } else { // 如果待插入节点小于等于当前节点， 则将该节点插入当前节点的左子树。
            BinaryTree<T> leftChild = root.getLeftChild();
            if (leftChild == null) {
                root.setLeftChild(new BinaryTree(data));
            } else {
                insert(leftChild, data);
            }
        }

    }

    /**
     * 向二叉树中插入子节点,若isAscend=true,二叉树的根节点都比右节点小，若isAscend=false,二叉树的根节点都比左节点小， 构建一棵二叉排序树
     * 此为递归实现， 思考：如果不使用递归， 如何实现？
     *
     * @param root     树根节点
     * @param data     待插入节点
     * @param isAscend 是否升序， true是， false 否 前提是compareTo方法是增序实现
     */
    public static <T extends Comparable> void insert(BinaryTree<T> root, T data, boolean isAscend) {
        // 如果满足如下条件， 则将该节点插入当前节点的右子树。
        boolean ascend = (data.compareTo(root.getData()) > 0 && isAscend) || (data.compareTo(root.getData()) <= 0 && !isAscend);
        if (ascend) {
            BinaryTree<T> rightChild = root.getRightChild();
            if (rightChild == null) {
                root.setRightChild(new BinaryTree(data));
            } else {
                insert(rightChild, data, isAscend);
            }
        } else { // 如果不满足上述条件， 则将该节点插入当前节点的左子树。
            BinaryTree<T> leftChild = root.getLeftChild();
            if (leftChild == null) {
                root.setLeftChild(new BinaryTree(data));
            } else {
                insert(leftChild, data, isAscend);
            }
        }

    }

    /**
     * 根据给定的array, 创建排序二叉树， 以array[0]为root 默认升序
     *
     * @param array
     */
    public static <T extends Comparable> BinaryTree<T> create(T[] array) {
        if (array == null || array.length == 0) {
            return null;
        }

        BinaryTree<T> root = new BinaryTree(array[0]);
        List<T> subList = Arrays.asList(array).subList(1, array.length);
        for (T t : subList) {
            insert(root, t);
        }

        return root;
    }

    /**
     * 根据给定的array, 创建排序二叉树， 以array[0]为root
     *
     * @param array
     * @param isAscend true 升序， false-降序
     */
    public static <T extends Comparable> BinaryTree<T> create(T[] array, boolean isAscend) {
        if (array == null || array.length == 0) {
            return null;
        }

        BinaryTree<T> root = new BinaryTree(array[0]);
        List<T> subList = Arrays.asList(array).subList(1, array.length);
        for (T t : subList) {
            insert(root, t, isAscend);
        }

        return root;
    }

    /**
     * 递归先根遍历二叉树
     *
     * @param current
     */
    public static <T extends Comparable> void preOrder(BinaryTree<T> current) {
        if (current == null) {
            return;
        }

        visit(current);
        preOrder(current.getLeftChild());
        preOrder(current.getRightChild());
    }

    /**
     * 递归中根遍历二叉树
     *
     * @param current
     */
    public static <T extends Comparable> void inOrder(BinaryTree<T> current) {
        if (current == null) {
            return;
        }

        inOrder(current.getLeftChild());
        visit(current);
        inOrder(current.getRightChild());
    }

    /**
     * 递归后根遍历二叉树
     *
     * @param current
     */
    public static <T extends Comparable> void postOrder(BinaryTree<T> current) {
        if (current == null) {
            return;
        }

        postOrder(current.getLeftChild());
        postOrder(current.getRightChild());
        visit(current);
    }


    //=================================上递归， 下非递归分界线=======================================================

    /**
     * 非递归先根遍历二叉树1
     *
     * @param current
     */
    public static <T extends Comparable> void preOrderNoRecursion(BinaryTree<T> current) {
        if (current == null) {
            return;
        }

        Stack<BinaryTree<T>> stack = new Stack<>();
        stack.push(current);

        while (!stack.empty()) {
            current = stack.pop();
            visit(current);
            BinaryTree<T> rightChild = current.getRightChild();
            if (rightChild != null) {
                stack.push(rightChild);
            }
            BinaryTree<T> leftChild = current.getLeftChild();
            if (leftChild != null) {
                stack.push(leftChild);
            }
        }

    }

    /**
     * 非递归中根遍历二叉树1
     *
     * @param current
     */
    public static <T extends Comparable> void inOrderNoRecursion(BinaryTree<T> current) {
        Stack<BinaryTree<T>> stack = new Stack<>();

        while (current != null) {
            while (current != null) {
                BinaryTree<T> rightChild = current.getRightChild();
                if (rightChild != null) {
                    stack.push(rightChild);
                }
                stack.push(current);
                current = current.getLeftChild();
            }

            current = stack.pop();

            while (!stack.empty() && current.getRightChild() == null) {
                visit(current);
                current = stack.pop();
            }

            visit(current);
            if (!stack.empty()) {
                current = stack.pop();
            } else {
                current = null;
            }
        }
    }

    /**
     * 非递归实现后序遍历1
     *
     * @param current
     */
    public static <T extends Comparable> void postOrderNoRecursion(BinaryTree<T> current) {
        BinaryTree<T> visited = current;
        Stack<BinaryTree<T>> stack = new Stack<>();

        // 左子树入栈
        while (current != null) {
            for (; current.getLeftChild() != null; current = current.getLeftChild()) {
                stack.push(current);
            }

            // 当前节点无右子或右子已经输出
            while (current != null && (current.getRightChild() == null || current.getRightChild() == visited)) {
                visit(current);
                //记录上一个已输出节点
                visited = current;
                if (stack.empty()) {
                    return;
                }
                current = stack.pop();
            }

            // 处理右子节点
            stack.push(current);
            current = current.getRightChild();

        }
    }

    /**
     * 非递归先根遍历二叉树2
     * 压入所有的左节点，压入前访问它。左节点压入完后pop访问右节点。
     * 像这样算法时思考规律性的东西在哪。
     * 不管哪个节点都要压左节点判断右节点。
     *
     * @param current
     */
    public static <T extends Comparable> void preOrderNoRecursion2(BinaryTree<T> current) {
        Stack<BinaryTree<T>> stack = new Stack<>();

        while (current != null || !stack.empty()) {
            while (current != null) {
                visit(current);
                stack.push(current);
                current = current.getLeftChild();
            }

            if (!stack.empty()) {
                current = stack.pop();
                current = current.getRightChild();
            }
        }
    }

    /**
     * 非递归中根遍历二叉树2
     *
     * @param current
     */
    public static <T extends Comparable> void inOrderNoRecursion2(BinaryTree<T> current) {
        Stack<BinaryTree<T>> stack = new Stack<>();

        while (current != null || !stack.empty()) {
            while (current != null) {
                stack.push(current);
                current = current.getLeftChild();
            }

            if (!stack.empty()) {
                current = stack.pop();
                // 与preOrderNoRecursion2比较只有这句话的位置不一样，弹出时再访问。
                visit(current);
                current = current.getRightChild();
            }
        }
    }

    /**
     * 双栈法
     * 非递归实现后序遍历2
     *
     * @param root
     */
    public static <T extends Comparable> void postOrderNoRecursion2(BinaryTree<T> root) {

        Stack<BinaryTree<T>> leftStack = new Stack<>();
        Stack<BinaryTree<T>> rightStack = new Stack<>();
        BinaryTree<T> current = root, right;
        do {
            while (current != null) {
                right = current.getRightChild();
                leftStack.push(current);
                rightStack.push(right);
                current = current.getLeftChild();
            }

            current = leftStack.pop();
            right = rightStack.pop();

            if (right == null) {
                visit(current);
            } else {
                leftStack.push(current);
                rightStack.push(null);
            }

            current = right;
        } while (!leftStack.empty() || !rightStack.empty());
    }

    /**
     * 单栈法
     * 非递归实现后序遍历3
     *
     * @param root
     */
    public static <T extends Comparable> void postOrderNoRecursion3(BinaryTree<T> root) {
        Stack<BinaryTree<T>> stack = new Stack<>();
        BinaryTree<T> current = root, visited = root;
        while (current != null || !stack.empty()) {
            while (current != null) {
                stack.push(current);
                current = current.getLeftChild();
            }

            if (!stack.empty()) {
                BinaryTree<T> temp = stack.peek().getRightChild();
                if (temp == null || temp == visited) {
                    current = stack.pop();
                    visit(current);
                    visited = current;
                    current = null;
                } else {
                    current = temp;
                }
            }
        }
    }

    /**
     * 双栈法
     * 非递归实现后序遍历4
     *
     * @param root
     */
    public static <T extends Comparable> void postOrderNoRecursion4(BinaryTree<T> root) {
        Stack<BinaryTree<T>> stack = new Stack<>();
        Stack<BinaryTree<T>> temp = new Stack<>();
        BinaryTree<T> current = root;
        while (current != null || !temp.empty()) {
            while (current != null) {
                stack.push(current);
                temp.push(current);
                current = current.getRightChild();
            }

            if (!temp.empty()) {
                current = temp.pop();
                current = current.getLeftChild();

            }
        }

        while (!stack.empty()) {
            current = stack.pop();
            visit(current);
        }
    }

    /**
     * 访问节点
     *
     * @param bt
     * @param <T>
     */
    private static <T extends Comparable> void visit(BinaryTree<T> bt) {
        System.out.print(bt.getData() + "--");
    }
}



















